#include <iostream>
#include <assert.h>

using namespace std;

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};


// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
	typedef AVLTreeNode<T> Node;
public:
	AVLTree() //构造
		: _pRoot(nullptr)
	{}

	// 在AVL树中插入值为data的节点
	bool Insert(const T& data)
	{
		if (_pRoot == nullptr) {
			_pRoot = new Node(data);
			return true;
		}

		Node* pCur = _pRoot, * pParent = nullptr;
		while (pCur) {
			pParent = pCur;
			if (pCur->_data > data) pCur = pCur->_pLeft;
			else if (pCur->_data < data) pCur = pCur->_pRight;
			else return false;
		}

		// 插入新节点
		pCur = new Node(data);
		if (pParent->_data > data)
			pParent->_pLeft = pCur;
		else
			pParent->_pRight = pCur;
		pCur->_pParent = pParent;

		while (pParent)
		{
			// 更新pParent的平衡因子
			if (pCur == pParent->_pLeft)
				pParent->_bf--;
			else
				pParent->_bf++;

			if (pParent->_bf == 0)
				break;
			else if (pParent->_bf == -1|| pParent->_bf == 1)
			{
				pCur = pParent;
				pParent = pCur->_pParent;
			}
			else
			{
				// pParent->_bf: 2 || -2
				// pParent的节点失去平衡
				if (pParent->_bf == 2)
				{
					// 右子树高-->最后必须左单旋
					if (pCur->_bf == 1)
						RotateL(pParent);
					else
						RotateRL(pParent);
				}
				else
				{
					if (pCur->_bf == -1)
						RotateR(pParent);
					else
						RotateLR(pParent);
				}

				break;
			}
		}
		return true;
	
	}

	void InOrder()
	{
		_InOrder(_pRoot);
	}

	Node* LeftMost()
	{
		if (nullptr == _pRoot)
			return nullptr;

		Node* pCur = _pRoot;
		while (pCur->_pLeft)
			pCur = pCur->_pLeft;

		return pCur;
	}

	Node* RightMost()
	{
		if (nullptr == _pRoot)
			return nullptr;

		Node* pCur = _pRoot;
		while (pCur->_pRight)
			pCur = pCur->_pRight;

		return pCur;
	}

	// AVL树的验证
	bool IsAVLTree()
	{
		return _IsAVLTree(_pRoot);
	}

private:
	// 根据AVL树的概念验证pRoot是否为有效的AVL树
	bool _IsAVLTree(Node* pRoot)
	{
		if (pRoot == nullptr) return true;
		int lh = _Height(pRoot->_pLeft), rh = _Height(pRoot->_pRight);
		if (abs(rh - lh) >= 2 || rh - lh != pRoot->_bf) return false;

		return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
	}
	size_t _Height(Node* pRoot)
	{
		if (pRoot == nullptr) return 0;
		size_t lh = _Height(pRoot->_pLeft);
		size_t rh = _Height(pRoot->_pRight);
		return lh > rh ? lh + 1 : rh + 1;
	}
	// 右单旋
	void RotateR(Node* pParent)
	{
		Node* pSubL = pParent->_pLeft, * pSubLR = pSubL->_pRight;
		Node* pPParent = pParent->_pParent;
		
		pParent->_pLeft = pSubLR;
		if (pSubLR) pSubLR->_pParent = pParent;


		pSubL->_pRight = pParent;
		pParent->_pParent = pSubL;
		pSubL->_pParent = pPParent;

		if (pPParent == nullptr) {
			_pRoot = pSubL;
		}
		else {
			if (pPParent->_pLeft == pParent) pPParent->_pLeft = pSubL;
			else pPParent->_pRight = pSubL;
		}

		pParent->_bf = pSubL->_bf = 0;
	}
	// 左单旋
	void RotateL(Node* pParent)
	{
		Node* pSubR = pParent->_pRight, * pSubRL = pSubR->_pLeft;
		Node* pPParent = pParent->_pParent;

		pParent->_pRight = pSubRL;
		if (pSubRL) pSubRL->_pParent = pParent;
		
		pSubR->_pLeft = pParent;
		pParent->_pParent = pSubR;
		pSubR->_pParent = pPParent;

		if (pPParent == nullptr) {
			_pRoot = pSubR;
		}
		else {
			if (pPParent->_pLeft == pParent) pPParent->_pLeft = pSubR;
			else pPParent->_pRight = pSubR;
		}
		pParent->_bf = pSubR->_bf = 0;
	}
	// 右左双旋
	void RotateRL(Node* pParent)
	{
		Node* pSubR = pParent->_pRight, * pSubRL = pSubR->_pLeft;
		int bf = pSubRL->_bf;

		RotateR(pParent->_pRight);
		RotateL(pParent);
		 
		//更新部分节点的平衡因子
		if (bf == -1) pSubR->_bf = 1;
		else if (bf == 1)pParent->_bf = -1;
		

	}
	// 左右双旋
	void RotateLR(Node* pParent)
	{
		Node* pSubL = pParent->_pLeft, * pSubLR = pSubL->_pRight;
		int bf = pSubLR->_bf;

		RotateL(pParent->_pLeft);
		RotateR(pParent);

		//更新部分节点的平衡因子
		if (bf == 1)pSubL->_bf = 1;
		else if (bf == -1)pParent->_bf = 1;
	}

	void _InOrder(Node* pRoot)
	{
		if (pRoot)
		{
			_InOrder(pRoot->_pLeft);
			cout << pRoot->_data << " ";
			_InOrder(pRoot->_pRight);
		}
	}

private:
	Node* _pRoot;
};



void TestAVLTree()
{
	AVLTree<int> t;
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	for (auto e : a)
	{
		t.Insert(e);
	}

	t.InOrder();
	cout << endl;

	printf("最左边节点为：%d，最右边节点为：%d\n", t.LeftMost()->_data, t.RightMost()->_data);
	if (t.IsAVLTree()) printf("AVL树建立成功\n");
	else printf("AVL树建立失败\n");

}


int main()
{
	TestAVLTree();
    return 0;
}